from __future__ import division

import math
import random

#from scipy import mean
def mean(seq):
    'in pypy we have no scipy.. no scipy.mean() :(...'
    return sum(seq)/len(seq)



# A set of utilities for using a map imported from the openstreetmap project
# Written by Shaul Markovitch
# 17/11/2013: added a seed
DEFAULT_DB_FILE = "israel.csv"


DRIVEABLE_HIGHWAYS=['motorway','motorway_link','trunk','trunk_link',
                    'primary','primary_link','secondary','secondary_link',
                    'tertiary','tertiary_link','living_street','residential',
                    'unclassified']


SPEED_RANGES = [
                (80,120),   #'motorway'
                (80,100),   #'motorway_link'
                (70,110),   #'trunk'
                (70,90),    #'trunk_link'
                (60,100),   #'primary'
                (60,80),    # 'primary_link'
                (50,90),    #'secondary'
                (50,70),    # 'secondary_link'
                (40,80),    #'tertiary'
                (40,60),    # 'tertiary_link'
                (20,50),    #'living_street'
                (20,50),    #'residential'
                (30,90)     #'unclassified'
                ]
DEFAULT_HIGHWAY_TYPE =    12     #'unclassified'
DEFAULT_MINIMUM_DISTANCE = 50


#CHANGE_PROBABILITY = 0.1
#MAX_NUMBER_OF_CHANGE_EVENTS = 5
#MAX_CHANGE = 0.5
#GLOBAL_CHANGE_PROBABILITY = 0.1

class Link:
    """
    Contains information about a Link from a Junction to another Junction.
    If the road is two-way, there will be a separate Link from the other Junction.
    The target is the key of the taget Junction.
    The distance is in meters.
    The highway type is one of the keys in the SPEED_RANGES list.
    """
    def __init__(self, source,target, distance, highway_type = None, speed = None):
        self.source = source
        self.target = target
        self.distance = distance
        #self.name = name
        if highway_type == None:
            self.highway_type = DEFAULT_HIGHWAY_TYPE
        else:   
            self.highway_type = highway_type
        if speed == None:
            self.speed = self.DefaultSpeed(self.highway_type)
        else:
            self.speed = speed
            
    def DefaultSpeed(self,type_):
        limits = SPEED_RANGES[type_]
        return (limits[0]+limits[1])/2

    def CalcTime(self):
        # distance is in meters, speed is in km/h. we want time in seconds, so we multiply by 3.6
        return self.distance / self.speed * 3.6

    def __repr__(self):
        return "Link({source}, {target}, distance = {distance}, speed = {speed})".format(**self.__dict__)


            
class Junction: 
    """
    Contains information about a single Junction.  The latitude and
    longitude, the type,
    and the list of links to other junctions
    """ 
    def __init__(self,lat,lon,key,links=[]):
        self.lat = lat
        self.lon = lon
        #self.name = name
        #self.junction_type = junction_type
        self.links = links
        self.key = key

    def __repr__(self):
        return "Junction({lat}, {lon})".format(**self.__dict__)

    def __eq__(self, other):
        'compare lat/lon'
        if isinstance(other, Junction):
            return (self.lat == other.lat) and (self.lon == other.lon)
        return NotImplemented

    def __ne__(self, other):
        result = self.__eq__(other)
        if result is NotImplemented:
            return result
        return not result
        


class CountryMap:
    """
    The main class.  All the information is stored in the self.junctions
    dictionary, which contains the set of all Junction instances, hashed by their keys.
    The keys are the ids (integers interpreted as strings) given in the openstreetmap
    db to allow debugging.
    """
    def __init__(self):
        self.junctions = []
        self.speed_ranges = SPEED_RANGES
        self.minimum_distance_for_problem = DEFAULT_MINIMUM_DISTANCE
    
    def GetJunction(self,junction_key):
        return self.junctions[junction_key]
                
        
    def ComputeDistance(self,lat1, long1, lat2, long2):
        """
        The code for the ComputeDistance function was borrowed from 
        http://www.johndcook.com/python_longitude_latitude.html
        distance is in KM
        """
        if (lat1 == lat2 and long1 == long2):
            return 0.0
        if max(abs(lat1-lat2),abs(long1-long2)) < 0.00001:
            return 0.001
                
        # Convert latitude and longitude to 
        # spherical coordinates in radians.
        degrees_to_radians = math.pi/180.0
        # phi = 90 - latitude
        phi1 = (90.0 - lat1)*degrees_to_radians
        phi2 = (90.0 - lat2)*degrees_to_radians
        #
        # theta = longitude
        theta1 = long1*degrees_to_radians
        theta2 = long2*degrees_to_radians
        #
        # Compute spherical distance from spherical coordinates.
        # 
        # For two locations in spherical coordinates 
        # (1, theta, phi) and (1, theta, phi)
        # cosine( arc length ) = 
        #    sin phi sin phi' cos(theta-theta') + cos phi cos phi'
        # distance = rho * arc length
        #
        cos = (math.sin(phi1)*math.sin(phi2)*math.cos(theta1 - theta2) + 
               math.cos(phi1)*math.cos(phi2))
        arc = math.acos( cos )
        #
        # Remember to multiply arc by the radius of the earth 
        # in your favorite set of units to get length.
        return arc * 6373

    def JunctionDistance(self,j1_key,j2_key):
        j1 = self.GetJunction(j1_key)
        j2 = self.GetJunction(j2_key)
        #TRM int() ??? it's because the link.distance is actualy floored also
        return int(self.ComputeDistance(j1.lat,j1.lon,j2.lat,j2.lon))
            
    def GenerateProblem(self):
        l = len(self.junctions)
        return [random.randrange(0,l),random.randrange(0,l)]

    
    def LoadMap(self,filename=DEFAULT_DB_FILE):
        print 'LoadMap... '
        f = open(filename)
        from progress import ProgressDisplay, SINGLE_LINE
        for line in ProgressDisplay(f, display=SINGLE_LINE):
        #for line in f:
                junc = line.strip().split(",")
                junc[0] = float(junc[0])
                junc[1] = float(junc[1])
                j = Junction(junc[0],junc[1], len(self.junctions))
                raw_links = junc[2].split("#")
                if raw_links == ['']:
                        raw_links = []
                interpreted_links = [[int(i) for i in l.split("@")] for l in raw_links]
                j.links = [Link(j.key,l[0],l[1],l[2]) for l in interpreted_links]
                self.junctions.append(j)
        #TODO uncomment!!!
        self.GenerateRandomTraficReport()
        self.MapStat()		
        print 'done'
        return self
          
    def GenerateRandomTraficReport(self):
        """
        Simulates trafic reports (Waze style).  Each Link is assigned
        a speed generated randomly uniformly over the range of speeds
        associated with the particular road type.
        """
        random.seed(0)
        for j in self.junctions:
            for l in j.links:
                limits = self.speed_ranges[l.highway_type]
                l.speed = random.randrange(limits[0],limits[1]+1)
        # reset seed to time to allow randomness
        random.seed()

    def MapStat(self):
        print "Number of junctions: %d" % (self._GetNumOfJunctions())
        print "Total links: %d" % (self._GetTotalLinks())
        print "Max branch factor: %d" % (self._GetMaxBranching())
        print "Average branching factor: %g" %(self.GetAvgBranching())
        print "Max distance: %d" % (self._GetMaxDistance())
        print "Min distance: %d" % (self._GetMinDistance())
        print "Average distance: %g" % (self.GetAvgDistance())
        print "Max speed: %d" %(self.GetMaxSpeed())
        print "Min speed: %d" %(self._GetMinSpeed())
        print "Average speed: %g" %(self.GetAvgSpeed())
        for k in range(len(DRIVEABLE_HIGHWAYS)):
            print  DRIVEABLE_HIGHWAYS[k], " :%d" %(self._GetTotalLinksOfType(k))

    def _GetNumOfJunctions(self):
        '''You need to return the total number of junctions '''
        return len(self.junctions)
        
    def _GetTotalLinks(self):
        '''You need to return the total number of links '''
        return sum(len(j.links) for j in self.junctions)
        
    def _GetMaxBranching(self):
        '''You need to return the maximal branching factor in a junction '''
        return max(len(j.links) for j in self.junctions)
    
    def GetAvgBranching(self):
        '''You need to return the average branching factor in a junction '''
        return mean([len(j.links) for j in self.junctions])
        
    def _GetMaxDistance(self):
        '''You need to return the maximal distance between two adjacent junctions '''
        return max(l.distance for j in self.junctions for l in j.links)
    
    def _GetMinDistance(self):
        '''You need to return the minimal distance between two adjacent junctions '''
        return min(l.distance for j in self.junctions for l in j.links)
    
    def GetAvgDistance(self):
        '''You need to return the average distance between two adjacent junctions '''
        return mean([l.distance for j in self.junctions for l in j.links])
  
    def GetMaxSpeed(self):
        '''You need to return the maximal speed over all links '''
        return max(l.speed for j in self.junctions for l in j.links)
    
    def _GetMinSpeed(self):
        '''You need to return the minimal speed over all links '''
        return min(l.speed for j in self.junctions for l in j.links)
    
    def GetAvgSpeed(self):
        '''You need to return the average speed over all links '''
        return mean([l.speed for j in self.junctions for l in j.links])
    
    def _GetTotalLinksOfType(self, k):
        '''You need to return the total links where the highway type is k '''
        return len([l for j in self.junctions for l in j.links if l.highway_type == k])
        
    

